import java.util.Scanner;

public class Test0503 {
    public static void main(String[] args) {
    	Scanner in=new Scanner(System.in);
    	int n=in.nextInt();
    	int m=in.nextInt();
    	int MOD=109;
    	int ret=n;
    	for(int i=0;i<m-1;i++) {
    		ret=ret*(n-1)%MOD;
    	}
    	System.out.println(ret);
    }

}
